/*
 * [35]  复杂链表的复制
 * 
 * A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
 * Return a deep copy of the list.

 * 
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

// Definition for singly-linked list.
struct RandomListNode
{
  int val;
  RandomListNode *next, *random;
  RandomListNode(int x) : val(x), next(NULL), random(NULL) {}
};

class Solution
{
public:
  // 在首结点head之前是头结点prehead
  RandomListNode *copyRandomList(RandomListNode *head)
  {
    // 第一步：复制一份结点与next指针
    RandomListNode *cur = head;
    while (cur != nullptr)
    {
      // 构造函数会将next和random指针赋值为null
      RandomListNode *node = new RandomListNode(cur->val);
      // 旧结点与新结点连接
      cur->next = node;
      // 新结点与旧结点连接
      node->next = cur->next;
      // 下个旧结点
      cur = node->next;
    }

    // 复制random指针
    cur = head;
    while (cur != nullptr)
    {
      if (cur->random != nullptr)
        // 复制random指针 (cur->next为新结点)
        cur->next->random = cur->random->next;

      // 下一个旧结点
      cur = cur->next->next;
    }

    // 第三步：拆分链表
    // cur是用来判断是否到卫兵位置
    // 创建整个链表的空头结点，方便处理
    // prehead不能是指针形式，你创建指针你得指向一个实体
    RandomListNode prehead(0);
    prehead.next = head;
    RandomListNode *newcur = &prehead;
    for (auto cur = head; cur; cur = cur->next->next)
    {
      // 先连接前面的指针
      newcur->next = cur->next;
      newcur = newcur->next;
    }

    return prehead.next;
  }
};

int main()
{
  class Solution solute;
  // ListNode *prehead = new ListNode(-1);

  // ListNode *head = new ListNode(1);
  // prehead->pnext = head;

  // ListNode *node2 = new ListNode(2);
  // head->pnext = node2;
  // node2->pnext = nullptr;

  // ListNode *node3 = new ListNode(2);
  // node2->pnext = node3;
  // node3->pnext = nullptr;

  // ListNode *node4 = new ListNode(3);
  // node3->pnext = node4;
  // node4->pnext = nullptr;

  // ListNode *node5 = new ListNode(5);
  // node4->pnext = node5;
  // node5->pnext = nullptr;

  // ListNode *prehead2 = new ListNode(-1);

  // ListNode *head2 = new ListNode(1);
  // prehead2->pnext = head2;

  // ListNode *node_2 = new ListNode(2);
  // head2->pnext = node_2;
  // node_2->pnext = nullptr;

  //ListNode *entry = solute.mergeTwoLists(head, head2);

  return 0;
}

// @lc code=end
